/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Microsoft
 * Date: 2023-03-02
 * Time: 14:24
 */
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Microsoft
 * Date: 2023-02-28
 * Time: 10:46
 */
public class Test{
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(3);
        myLinkedList.display();
        myLinkedList.clear();
        myLinkedList.display();
    }



    /**
     * 判断两个链表是否有公共节点
     * @param headA
     * @param headB
     * @return
     */
    public MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        //1.分别求两个链表的长度
        int lenA = 0;
        int lenB = 0;
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;

        //计算pl的长度
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        //计算ps的长度
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }

        //2.将pl和ps指回来
        //当pl和ps遍历完以后，pl和ps都是null，当len大于0的时候，那么pl和ps依旧是null，当len小于0的时候，那么pl和ps才会是对应头节点的引用
        pl = headA;
        ps = headB;

        //3.根据length的值修改pl和ps的指向
        int len = lenA - lenB;
        if (len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }//1.这样能保证len一定是一个正数 2.pl指向的链表一定是长的 3.ps指向的链表一定是短的

        //让pl指向的链表先走len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        //pl和ps同时走
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
    /*        //当pl和ps走到这里的时候，说明pl == ps ，有可能二者为null
        if (pl == ps && pl == null) {
            return null;
        }
        return pl;*/
        return pl;//可以直接返回pl，无论pl为空或者某个节点的地址
    }


    /**
     * 合并两个有序列表
     * @param head1
     * @param head2
     * @return
     */
    public MySingleList.ListNode mergeTwoLists
            (MySingleList.ListNode head1, MySingleList.ListNode head2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(0);
        MySingleList.ListNode tmp = newHead;

        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
                tmp = tmp.next;
            }else {
                tmp.next = head2;
                head2 = head2.next;
                tmp = tmp.next;
            }
        }
        if (head1 != null) {
            tmp.next = head1;
        }
        if (head2 != null) {
            tmp.next = head2;
        }
        return newHead.next;

    }
    public static void main2(String[] args) {

    }
}

















